package mid.class1;

import java.util.Arrays;

/**
 * 数组种两个数的最大异或值
 */
public class Code08_xorMaxNumber {
    public static void main(String[] args) {
        int[] nums = {2, 4, 8, 1};
        ArrayTrie trie = new ArrayTrie();
        trie.build(nums);
        int ans = 0;
        for (int num : nums) {
            ans = Math.max(ans, trie.maxXor(num));
        }
        System.out.println("ans = " + ans);
    }


    private static class ArrayTrie {
        private int m = 2;
        public int[][] tree = new int[20][m];

        private int cnt;
        public int left;

        public ArrayTrie() {
            this.cnt = 1;
        }

        public int maxXor(int num) {
            int ans = 0;
            int cur = 1;
            for (int i = left, status, want; i >= 0; i--) {
                status = (num >> i) & 1;
                want = status ^ 1;
                if (tree[cur][want] == 0) {
                    want ^= 1;
                }
                ans |= (status ^ want) << i;
                cur = tree[cur][want];
            }
            return ans;
        }

        public void build(int[] nums) {
            cnt = 1;
            int max = Integer.MIN_VALUE;
            for (int num : nums) {
                max = Math.max(num, max);
            }

            left = 31 - Integer.numberOfLeadingZeros(max);
            for (int num : nums) {
                insert(num);
            }
        }

        public int path(char c) {
            if (c == '#') {
                return 10;
            } else if (c == '-') {
                return 11;
            } else {
                return c - '0';
            }
        }

        public void insert(int num) {
            int cur = 1;
            for (int i = left, path; i >= 0; i--) {
                path = num >> i & 1;
                if (tree[cur][path] == 0) {
                    tree[cur][path] = ++cnt;
                }
                cur = tree[cur][path];
            }
        }


        public void clear() {
            for (int i = 0; i < cnt; i++) {
                Arrays.fill(tree[i], 0);
            }
        }
    }
}
